﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

     * */
    class Problem71 : IProblem
    {
        public string Calculate()
        {
            //ultrabezveze

            double fraction = 3 / 7.0;

            double mindifference = 1;
            int min_numerator = 7;

            for (int d = 8; d <= 1000000; d++)
            {
                int inverse = (int)(d * fraction);

                if (CommonFunctions.GreatestCommonDivisor(d, inverse) != 1)
                    inverse--;

                double current = inverse / (double)d;
                double difference = fraction - current;

                if (difference < mindifference)
                {
                    mindifference = difference;
                    min_numerator = inverse;
                }
            }


            return min_numerator.ToString();
        }
    }
}
